CPS (continuation-passing style, 継続渡し方式)

継続はコントロールフローとして見ることもでき､CPSへの変換によってfor文やearly return､例外なども表現できる｡

基本例

code: haskell

show "hello, world"

===

(\k -> (\k' -> k' showK ) $ \show -> (\k'' -> k'' "hello, world") (\str -> show str k)) id

where showK s k = k . show $ s -- (showをビルトイン関数と見ると) ビルトイン関数は手動で継続を受け取るように変換する

型なしラムダ計算のCPS変換

$ \begin{array}{rcl} \left\lceil \lambda x. e \right\rceil & = & \lambda k. k \left(\lambda x\ k'. \left\lceil e\right\rceil k'\right) \\ \left\lceil x \right\rceil & = & \lambda k. k\ x \\ \left\lceil e_1\ e_2\right\rceil & = & \lambda k. \left\lceil e_1\right\rceil \left( \lambda f. \left\lceil e_2\right\rceil \left(\lambda v'. f\ v'\ k \right) \right)\end{array}

利用例

SML/NJ

多くのScheme実装

参考文献

Appel, Andrew W. Compiling with continuations. Cambridge University Press, 2006.